{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"color:#777777;background-color:#ffffff;font-size:12px;text-align:right;\">\n",
    "\tprepared by Abuzer Yakaryilmaz (QuSoft@Riga) | November 07, 2018\n",
    "</div>\n",
    "<table><tr><td><i> I have some macros here. If there is a problem with displaying mathematical formulas, please run me to load these macros.</i></td></td></table>\n",
    "$ \\newcommand{\\bra}[1]{\\langle #1|} $\n",
    "$ \\newcommand{\\ket}[1]{|#1\\rangle} $\n",
    "$ \\newcommand{\\braket}[2]{\\langle #1|#2\\rangle} $\n",
    "$ \\newcommand{\\inner}[2]{\\langle #1,#2\\rangle} $\n",
    "$ \\newcommand{\\biginner}[2]{\\left\\langle #1,#2\\right\\rangle} $\n",
    "$ \\newcommand{\\mymatrix}[2]{\\left( \\begin{array}{#1} #2\\end{array} \\right)} $\n",
    "$ \\newcommand{\\myvector}[1]{\\mymatrix{c}{#1}} $\n",
    "$ \\newcommand{\\myrvector}[1]{\\mymatrix{r}{#1}} $\n",
    "$ \\newcommand{\\mypar}[1]{\\left( #1 \\right)} $\n",
    "$ \\newcommand{\\mybigpar}[1]{ \\Big( #1 \\Big)} $\n",
    "$ \\newcommand{\\sqrttwo}{\\frac{1}{\\sqrt{2}}} $\n",
    "$ \\newcommand{\\dsqrttwo}{\\dfrac{1}{\\sqrt{2}}} $\n",
    "$ \\newcommand{\\onehalf}{\\frac{1}{2}} $\n",
    "$ \\newcommand{\\donehalf}{\\dfrac{1}{2}} $\n",
    "$ \\newcommand{\\hadamard}{ \\mymatrix{rr}{ \\sqrttwo & \\sqrttwo \\\\ \\sqrttwo & -\\sqrttwo }} $\n",
    "$ \\newcommand{\\vzero}{\\myvector{1\\\\0}} $\n",
    "$ \\newcommand{\\vone}{\\myvector{0\\\\1}} $\n",
    "$ \\newcommand{\\vhadamardzero}{\\myvector{ \\sqrttwo \\\\  \\sqrttwo } } $\n",
    "$ \\newcommand{\\vhadamardone}{ \\myrvector{ \\sqrttwo \\\\ -\\sqrttwo } } $\n",
    "$ \\newcommand{\\myarray}[2]{ \\begin{array}{#1}#2\\end{array}} $\n",
    "$ \\newcommand{\\X}{ \\mymatrix{cc}{0 & 1 \\\\ 1 & 0}  } $\n",
    "$ \\newcommand{\\Z}{ \\mymatrix{rr}{1 & 0 \\\\ 0 & -1}  } $\n",
    "$ \\newcommand{\\Htwo}{ \\mymatrix{rrrr}{ \\frac{1}{2} & \\frac{1}{2} & \\frac{1}{2} & \\frac{1}{2} \\\\ \\frac{1}{2} & -\\frac{1}{2} & \\frac{1}{2} & -\\frac{1}{2} \\\\ \\frac{1}{2} & \\frac{1}{2} & -\\frac{1}{2} & -\\frac{1}{2} \\\\ \\frac{1}{2} & -\\frac{1}{2} & -\\frac{1}{2} & \\frac{1}{2} } } $\n",
    "$ \\newcommand{\\CNOT}{ \\mymatrix{cccc}{1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 0 & 1 \\\\ 0 & 0 & 1 & 0} } $\n",
    "$ \\newcommand{\\norm}[1]{ \\left\\lVert #1 \\right\\rVert } $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> Probabilistic Operators</h2>\n",
    "\n",
    "Remember Asja's biased coins, and her coin-flipping protocol.\n",
    "\n",
    "$\n",
    "GameCoins = \\begin{array}{c|cc} & \\mathbf{Head} & \\mathbf{Tail} \\\\ \\hline \\mathbf{Head} & 0.6 & 0.3\\\\  \\mathbf{Tail} & 0.4 & 0.7  \\end{array} = \\begin{array}{c|cc} & \\mathbf{0} & \\mathbf{1} \\\\ \\hline \\mathbf{0} & 0.6 & 0.3 \\\\  \\mathbf{1} & 0.4 & 0.7  \\end{array}\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's trace Asja's outcomes after two coin flips.\n",
    "\n",
    "<b> At the beginning: </b>\n",
    "\n",
    "<i> Remember the protocol:\n",
    "<ol> \n",
    "    <li> she starts with flipping one euro, </li>\n",
    "    <li> whenever she gets a head, she flips one euro, and </li>\n",
    "    <li> whenever she gets a tail, she flips one cent. </li>\n",
    "</ol>\n",
    "</i>\n",
    "\n",
    "She starts in state $ \\myvector{1 \\\\ 0} $.\n",
    "\n",
    "State 0 represents Head and state 1 represents Tail."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>After one coin flip:</b>\n",
    "\n",
    "The probabilities of getting head and tail are $0.6$ and $ 0.4 $. Thus, the new state is $ \\myvector{0.6 \\\\ 0.4} $.\n",
    "\n",
    "<b>After two coin flip:</b>\n",
    "\n",
    "The probabilities of getting head and tail are\n",
    "\n",
    "$$\n",
    "    \\begin{array}{lclcl}\n",
    "    0.6 Head & \\rightarrow & 0.36 Head & + & 0.24 Tail \n",
    "    \\\\\n",
    "    0.4 Tail & \\rightarrow & 0.12 Head & + & 0.28 Tail\n",
    "    \\\\\n",
    "    Total: & & 0.48 Head & + & 0.52 Tail\n",
    "    \\end{array}   \n",
    "    ~~~~~~~~~~~~~~~~~~~~~\n",
    "    \\mypar{ \n",
    "        GameCoins = \\begin{array}{c|cc} & \\mathbf{Head} & \\mathbf{Tail} \\\\ \\hline \\mathbf{Head} & 0.6 & 0.3\\\\  \\mathbf{Tail} & 0.4 & 0.7  \\end{array}\n",
    "        }\n",
    "$$\n",
    "\n",
    "Thus the new state is $ \\myvector{0.48 \\\\ 0.52} $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>Coin-flipping protocol</b> of Asja is a <i>probabilistic operator</i>.\n",
    "\n",
    "Similar to any operator, depending on the current state, Asja's coin-flipping protocol determines the next state.\n",
    "\n",
    "$$\n",
    "    \\myvector{1 \\\\ 0} \\xrightarrow{\\mbox{Asja's coin-flipping protocol}} \\myvector{0.6 \\\\ 0.4}\n",
    "    \\xrightarrow{\\mbox{Asja's coin-flipping protocol}}  \\myvector{0.48 \\\\ 0.52}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=\"blue\"><b>A probabilistic operator evolves the system from any given probabilistic state to a probabilistic state.</b></font>\n",
    "\n",
    "For example, Asja's coin-flipping protocol transforms $ \\myvector{ 0.8 \\\\ 0.2 } $ to $ \\myvector{ 0.54 \\\\ 0.46 } $.\n",
    "\n",
    "For the new state, we use the table $  GameCoins = \\begin{array}{c|cc} & \\mathbf{Head} & \\mathbf{Tail} \\\\ \\hline \\mathbf{Head} & 0.6 & 0.3\\\\  \\mathbf{Tail} & 0.4 & 0.7  \\end{array} $ and the current state $ \\myvector{ 0.8 \\\\ 0.2 } $:\n",
    "\n",
    "$$\n",
    "    \\myvector{ \\myarray{c}{0.6 \\cdot 0.8 \\\\ + \\\\ 0.3 \\cdot 0.2} \\\\ \\hline \\myarray{c}{0.4 \\cdot 0.8 \\\\ + \\\\ 0.7 \\cdot 0.2} } = \\myvector{ \\myarray{c}{0.48 \\\\ + \\\\ 0.06} \\\\ \\hline \\myarray{c}{0.32 \\\\ + \\\\ 0.14}  } = \\myvector{ 0.54 \\\\ 0.46 }.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may notice that the first entry of the new probabilistic state is the summation of the pairwise multiplications between the entries of the first row in the table and the entries of the probabilistic state.\n",
    "<ul><li>The first row of the table represents the transitions from all states to the first state.</li>\n",
    "    <li> If the system is in the first state with probability $0.8$, then its contribution to the first state in the new probabilistic state is $ (0.6 \\cdot 0.8) = 0.48  $. </li>\n",
    "    <li> Similarly, the contribution of the second state to the first state is $ (0.3 \\cdot 0.2) = 0.06 $.</li>\n",
    "    <li> Then both contributions are added up, $ (0.48 + 0.06) = 0.54  $.</li>\n",
    "</ul>\n",
    "\n",
    "Similarly, the second entry of the new probabilistic state is the summation of the pairwise multiplications between the entries of the second row in the table and the entries of the probabilistic state.\n",
    "<ul><li>The second row of the table represents the transitions from all states to the second state.</li>\n",
    "    <li> The system is in the first state with probability $0.8$, then its contribution to the second state in the new probabilistic state is $ (0.4 \\cdot 0.8) = 0.32  $. </li>\n",
    "    <li> Similarly, the contribution of the second state to the second state is $ (0.7 \\cdot 0.2) = 0.14 $.</li>\n",
    "    <li> Then both contributions are added up, $ (0.32 + 0.14) = 0.46  $.</li>\n",
    "</ul>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=\"blue\"> You may have already noticed that this is a matrix-vector multiplication :-) </font>\n",
    "\n",
    "If we represent $ GameCoins $ as a matrix: $ \\mymatrix{cc}{ 0.6 & 0.3 \\\\ 0.4 & 0.7 } $, then the new probabilistic state is calculated as\n",
    "\n",
    "$$\n",
    "    \\myvector{ 0.54 \\\\ 0.46 } = \\mymatrix{cc}{ 0.6 & 0.3 \\\\ 0.4 & 0.7 } \\myvector{ 0.8 \\\\ 0.2 }.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Task 1 </h3>\n",
    "\n",
    "Please verify the multiplication."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Properties of a probabilistic operator</h3>\n",
    "\n",
    "What we have observed is generic for any probabilistic operator:\n",
    "<ul>\n",
    "    <li> A probabilistic operator can be represented as a matrix. </li>\n",
    "    <li> Its $ j $-th column represents the transitions probabilities from the $ j $-th state to all states. </li>\n",
    "    <li> Its $i$-th row represents the transitions probabilities from all states to the $ i $-th state.</li>\n",
    "    <li> Therefore, the entry in the $ j $-th column and $ i $-th row represents the transition probability from the $j$-th state to the $i$-th state. </li>\n",
    "</ul>\n",
    "\n",
    "Moreover,\n",
    "<ul>\n",
    "    <li> each entry of a probabilistic operator must be between 0 and 1, and </li>\n",
    "    <li> any column summation must be 1. </li>\n",
    "</ul>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>Task 2</h3>\n",
    "\n",
    "Randomly construct a $ (3 \\times 3 ) $-dimensional probabilistic operator.\n",
    "\n",
    "That is, randomly determine the entries of the matrix that represents a probabilistic operator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#\n",
    "# your solution is here\n",
    "#\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href=\"..\\bronze-solutions\\B36_Probabilistic_Operators_Solutions.ipynb#task2\">click for our solution</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>The evolution of a probabilistic system</h3>\n",
    "\n",
    "If a system is probabilistic,\n",
    "<ul>\n",
    "    <li>its state description at any time is probabilistic, and it is represented by a probabilistic state, and</li>\n",
    "    <li>its evolution is governed by probabilistic operators. </li>\n",
    "</ul>\n",
    "\n",
    "When the system is in the probabilistic state $ v $ and the probabilistic operator $ A $ is applied, then the new probabilistic state is\n",
    "\n",
    "$$\n",
    "    v' = A \\cdot v.\n",
    "$$\n",
    "\n",
    "The evolution of a probabilistic system is simplified to matrix vector multiplications."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Mathematical terms (names) </h3>\n",
    "\n",
    "There are mathematical terms for probabilistic state and operator.\n",
    "\n",
    "A <i> probabilistic state</i> is represented by a vector with nonnegative entries such that the summation of all entries is 1.\n",
    "\n",
    "A <i> probabilistic operator</i> is represented by a square* matrix with nonnegative entries such that the summation of every column is 1.\n",
    "\n",
    "Any such vector and matrix is also called <b>stochastic</b>.\n",
    "\n",
    "<i>*Sqaure matrix is a matrix having the same number of row(s) and column(s).</i>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Task 3 </h3>\n",
    "\n",
    "Write a function in python for Asja's probabilistic operator $ \\mymatrix{cc}{ 0.6 & 0.3 \\\\ 0.4 & 0.7 } $ such that\n",
    "<ul>\n",
    "    <li> it takes a probabilistic state as the input, and </li>\n",
    "    <li> it outputs the new probabilistic state.</li>\n",
    "</ul>\n",
    "   \n",
    "Then, test your function by applying it twice to the starting state $ \\myvector{1 \\\\ 0} $.\n",
    "\n",
    "Remember that: $ \n",
    "    \\myvector{1 \\\\ 0} \\xrightarrow{\\mbox{Asja's coin-flipping protocol}} \\myvector{0.6 \\\\ 0.4}\n",
    "    \\xrightarrow{\\mbox{Asja's coin-flipping protocol}}  \\myvector{0.48 \\\\ 0.52}.\n",
    "$\n",
    "\n",
    "If your function seems to work, then evolve your system for 3, 6, 9, 12, 24, 48, and 96 steps.\n",
    "\n",
    "Is there any pattern?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#\n",
    "# your solution is here\n",
    "#\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href=\"..\\bronze-solutions\\B36_Probabilistic_Operators_Solutions.ipynb#task3\">click for our solution</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Task 4 </h3>\n",
    "\n",
    "Write a function that takes a probabilistic operator and a probabilistic state, and then returns the new probabilistic state.\n",
    "\n",
    "Your function should work for any dimension.\n",
    "\n",
    "Test your function on $ \\mymatrix{ccc}{ 0.4 & 0.6 & 0 \\\\ 0.2 & 0.1 & 0.7 \\\\ 0.4 & 0.3 & 0.3 } $ and $ \\myvector{0.1 \\\\ 0.3 \\\\ 0.6} $. \n",
    "\n",
    "The new probabilistic state should be $ \\myvector{0.22 \\\\ 0.47 \\\\ 0.31} $.\n",
    "\n",
    "Then, evolve your system for 5, 10, 20, and 40 steps.\n",
    "\n",
    "The system should evolve to a fixed probabilistic state.\n",
    "\n",
    "Change your initial state to  $ \\myvector{1 \\\\ 0 \\\\ 0} $, and see whether the converged state is the same or not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# operator for the test\n",
    "A = [\n",
    "    [0.4,0.6,0],\n",
    "    [0.2,0.1,0.7],\n",
    "    [0.4,0.3,0.3]\n",
    "]\n",
    "\n",
    "# state for test\n",
    "v = [0.1,0.3,0.6]\n",
    "\n",
    "#\n",
    "# your solution is here\n",
    "#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href=\"..\\bronze-solutions\\B36_Probabilistic_Operators_Solutions.ipynb#task4\">click for our solution</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Two probabilistic bits </h3>\n",
    "\n",
    "Freivalds is a probabilistic system with two bits.\n",
    "\n",
    "Then it has four states: $ 00 $, $ 01 $, $ 10 $, and $ 11 $. \n",
    "\n",
    "If the first and second bits have two states, then they can be together in $ 2 \\cdot 2 = 4 $ different combinations of states:\n",
    "<ul>\n",
    "    <li> 00: both bits are zeros, </li>\n",
    "    <li> 01: the first bit is zero, and the second bit is one,</li>\n",
    "    <li> 10: the first bit is one, and the second bit is zero, and, </li>\n",
    "    <li> 11: both bits are ones. </li>\n",
    "    </ul>\n",
    "    \n",
    "Each different combination is a new state of the composite system, which is composed by two bits.\n",
    "\n",
    "<i> As another example, three bits form a system with $ 2 \\cdot 2 \\cdot 2 = 8 $ states: $ 000 $, $ 001 $, $ 010 $, $ 011 $, $ 100 $, $ 101 $, $ 110 $, and $ 111 $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Freivalds' initial state (Optional) </h3>\n",
    "\n",
    "Freivalds starts in state $ \\myvector{ 0.5 \\\\ 0 \\\\ 0.5 \\\\ 0 } $.\n",
    "\n",
    "Freivalds symbol by symbol reads the strings composed by $ a $s and $ b $s."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Freivalds reads symbol $ a $</h3>\n",
    "\n",
    "When reading an $ a $ and in the state $ 00 $, Freivalds goes to states $ 01 $ and $ 11 $ with probabilities $ 0.25 $ and stays in state $ 00 $ with probabilty $ 0.5 $. \n",
    "\n",
    "When reading an $ a $ and in any other state, Freivalds stays in the same state with probability 1.\n",
    "\n",
    "Thus, we can define a probabilistic operator $ A $ for the actions of reading an $ a $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>Task 5 </h3>\n",
    "\n",
    "Is A the following matrix?\n",
    "\n",
    "$$\n",
    "    A = \\mymatrix{rccc}{ 0.5 & 0 & 0 & 0 \\\\ 0.25 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0.25 & 0 & 0 & 1 }.\n",
    "$$\n",
    "\n",
    "<i> The columns and rows correspond to the states in order of $ 00 $, $ 01 $, $ 10 $, and $ 11 $.</i>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Freivalds reads symbol $ b $</h3>\n",
    "\n",
    "When reading a $ b $ and in the state $ 10 $, Freivalds goes to states $ 01 $ and $ 11 $ with probabilities $ 0.25 $ and stays in state $ 10 $ with probabilty $ 0.5 $. \n",
    "\n",
    "When reading a $ b $ and in any other state, Freivalds stays in the same state with probability 1.\n",
    "\n",
    "Thus, we can define a probabilistic operator $ B $ for the actions of reading a $ b $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>Task 6 </h3>\n",
    "\n",
    "Is B the following matrix?\n",
    "\n",
    "$$\n",
    "    B = \\mymatrix{rccc}{ 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0.25 & 0 \\\\ 0 & 0 & 0.5 & 0 \\\\ 0 & 0 & 0.25 & 1 }.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3> Task 7 </h3>\n",
    "\n",
    "A challenging task.\n",
    "\n",
    "Freivalds reads 50 random strings of length 40. \n",
    "\n",
    "Find the final probabilistic state for each string.\n",
    "\n",
    "Is there any relation between the numbers of $ a $s and $ b $s, say $ N_a $ and $ N_b $, and the probabilities of the first bit being in zero and one, say $ p_0 $ and $ p_1 $?\n",
    "<ul>\n",
    "    <li> When $ N_a > N_b $, then is $ p_0 < p_1 $ or $ p_0 > p_1 $? </li>\n",
    "    <li> When $ N_a < N_b $, then is $ p_0 < p_1 $ or $ p_0 > p_1 $? </li>\n",
    "</ul>\n",
    "\n",
    "Or simply check the signs of $ (N_a - N_b) $ and $ (p_0-p_1) $ for each string.\n",
    "\n",
    "<i>Note that the multiplication of two numbers with the same signs is a positive number, and the multiplication of two numbers with the opposite signs gives a negative number.</i>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the initial state\n",
    "initial = [0.5, 0, 0.5, 0]\n",
    "\n",
    "# probabilistic operator for symbol a\n",
    "A = [\n",
    "    [0.5,  0, 0, 0],\n",
    "    [0.25, 1, 0, 0],\n",
    "    [0,    0, 1, 0],\n",
    "    [0.25, 0, 0, 1]\n",
    "]\n",
    "\n",
    "# probabilistic operator for symbol b\n",
    "B = [\n",
    "    [1, 0, 0,    0],\n",
    "    [0, 1, 0.25, 0],\n",
    "    [0, 0, 0.5,  0],\n",
    "    [0, 0, 0.25, 1]\n",
    "]\n",
    "\n",
    "#\n",
    "# your solution is here\n",
    "#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href=\"..\\bronze-solutions\\B36_Probabilistic_Operators_Solutions.ipynb#task7\">click for our solution</a>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
